Witnessing Control Flow Graph Optimizations
- Project Research
- 1-5 Chapters
- Abstract : Available
- Table of Content: Available
- Reference Style: APA
- Recommended for : Student Researchers
- NGN 3000
ABSTRACT
Proving the correctness of a program transformation, and specifically, of a compiler optimization, is a long-standing research problem. Trusting the compiler requires to guarantee that the properties verified on the source program hold for the compiled target-code as well. Thus, the primary objective of formal correctness verification is to preserve the semantics of the source code, maintaining untouched its logical behavior. Traditional methods for formal correctness verification are not convenient to validate large and complex programs like compilers [1], and intensive testing, despite its proven efficacy, cannot guarantee the absence of bugs [2]. This thesis is part of a larger on-going research project aimed to demonstrate the feasibility to overcome the difficulties of traditional formal methods. K. Namjoshi and L. Zuck [3] propose a new methodology for creating an automated proof to guarantee the correctness of every execution of an optimization. A witness is a run-time generated relation between the source code and the target code, before and after the transformation. The relation is able to represent all the properties that must be valid throughout the optimization, offering a mathematical formula to prove, through a SMT-Solver (typically Microsoft Z3 ), if the invariants hold and the semantics is preserved. This work is a further step towards the implementation of a witnessing compiler [4]: the SimplifyCFG pass of the LLVM compiler framework is augmented with a witness generator procedure which constructs, run-time, the relations to prove the correctness of every single simplification in the control flow graph, performed by the compiler. We show that it is feasible to augment the SimplifyCFG pass with a witness generation procedure. We describe the structure of the code and the mathematical relations designed to demonstrate the correctness of a transformation on the Control Flow Graph. Benchmarks and tests will prove the correct behavior of our implementation and the effectiveness of the witnessing procedure. We provide details about the witnesses and the results of the benchmarks. First, the problem is described, together with the limitations of the traditional methods; then a solution is designed and explained. Details about the actual implementation for the SimplifyCFG code are provided in further sections
Related Project Materials
EFFECT OF GLYCEROL AND SHEA BUTTER ON THE PROPERTIES OF FILMS PRODUCED FROM CHITOSAN AND Borassus aethiopum STARCH COMPOSITES
ABSTRACT
The concern in environmental waste management and toxicity of petroleum derived plastics has led to the search for renewable, no...
REAL EXCHANGE RATE AND NON OIL EXPORT IN NIGERIA
Abstract
This study is on real exchange rate and non oil export in Nigeria. The total population for the study is 200 st...
AVAILABILITY AND ADEQUACY OF RESOURCES FOR EFFECTIVE DATA PROCESSING INSTRUCTION IN SECONDARY SCHOOL IN OJO LOCAL GOVERNMENT AREA OF LAGOS STATE
Background Of The Study
Education is critical to a country's economic growth because it aims to pro...
AN ASSESSMENT OF ORGANISATIONAL SUPPORT FOR MANAGEMENT EDUCATION AND TRAINING IN PRIVATE ORGANIZATIONS IN NIGERIA
BACKGROUND OF THE STUDY
Training is a vital component of human capital management and the fastest-growi...
PROBLEMS ENCOUNTERED BY MARRIED FEMALE SECRETARIES IN PARASTATALS
ABSTRACT
This research work is aimed at determining the problems of married female secretaries in some parastatals in En...
INFLUENCE OF INSTRUCTIONAL MATERIALS ON THE ACADEMIC PERFORMANCE OF STUDENTS IN AGRICULTURAL SCIENCE IN SECONDARY SCHOOLS IN KWARA STATE, NIGERIA
ABSTRACT
The study examined the availability of instructional materials, its adequacy and relevancy...
GRAMMATICAL ERRORS IN SECONDARY SCHOOL STUDENTS’ ENGLISH ESSAYS
ABSTRACT
This Research Work focused on the gramatical errors in the English essays of Secondary Schools Students. The re...
EFFECTS OF TEACHERS QUALIFICATION ON STUDENTS ACADEMIC PERFORMANCE IN SENIOR SECONDARY SCHOOLS
ABSTRACT
This study was carried out to examine the effects of teachers qualification on students academ...
FACTORS AFFECTING SECONDARY SCHOOL ORAL ENGLISH INSTRUCTION
Abstract
In English Language, there is a strong correlation between oral language skills and achievement in the written...
CHALLENGES IN TEACHING AND LEARNING OF PRACTICAL AGRICULTURE
Abstract
This study sought to investigate the challenges in teaching and learning of practical agriculture. 142 practica...
